"""
给定n行n列的整数矩阵A，其中每行的整数从左到右升序排列，
    每列的整数从上到下降序排列。即i,j∈{1,...,n-1}时，
    矩阵元素满足以下关系：A[i,j]<A[i,j+1]和A[i,j]>A[i+1,j]。
    给定一个整数x，试问矩阵A是否有整数x。
    例如：给定以下矩阵A，如果x=5，返回true；如果x=10返回false。
        A=  7 8 9
            3 4 6
            1 2 5
    请设计一个复杂度为O(n)的搜索算法。
"""


def mat_search(x, matA, left, right, up, down):
    while left <= right and up <= down:
        if x < matA[down][left] or x > matA[up][right]:
            return False
        if x == matA[up][left]:
            return True
        elif x > matA[up][left]:
            left += 1
        else:
            up += 1
        if x == matA[down][right]:
            return True
        elif x > matA[down][right]:
            down -= 1
        else:
            right -= 1
    return False


def matrix_search(x, matA):
    n = len(matA) - 1
    return mat_search(x, matA, 0, n, 0, n)


A = [[7, 8, 9], [3, 4, 6], [1, 2, 5]]

print(matrix_search(5, A), matrix_search(10, A))
